package suanfa;

import java.net.BindException;
import java.util.*;

/**
 * Description:
 * Author:    Dane
 * CreateTime:2024/8/28-上午11:10
 * Since  :   1.0
 * Version:   1.0
 */
public class Solution2 {

    public static int[] productExceptSelf(int[] nums) {

        int length = nums.length;
        int[] before = new int[length];
        int[] after = new int[length];
        int[] answer = new int[length];
        before[0] = 1;
        after[length - 1] = 1;
        for (int j = 1; j < length; j++) {
            before[j] = before[j - 1] * nums[j - 1];

        }
        for (int i = length - 2; i >= 0; i--) {
            after[i] = after[i + 1] * nums[i + 1];

        }
        for (int i = 0; i < length; i++) {
            answer[i] = before[i] * after[i];
        }


        return answer;

    }


    public int canCompleteCircuit2(int[] gas, int[] cost) {
        int sum = 0;
        int min = Integer.MAX_VALUE;
        int minIndex = -1;
        for (int i = 0; i < gas.length; i++) {
            sum = sum + gas[i] - cost[i];
            if (sum < min && sum < 0) {
                min = sum;
                minIndex = i;
            }
        }
        if (sum < 0) return -1;
        return (minIndex + 1) % gas.length;
    }

    public static int canCompleteCircuit3(int[] gas, int[] cost) {
//        int startIdx = 0; // 始发站
//        int curGas = 0; // 到达下一个加油站加油之前的累计剩余油量
//
//        for (int i = 0; i < gas.length; i++) {
//            curGas += gas[i] - cost[i];
//            if (curGas < 0) {
//                // 走不动了, 说明之前的始发站不行，从i+1重新出发
//                startIdx = i + 1;
//                curGas = 0;
//            }
//        }
//
//        // 判断累计剩余油量能否走完startIdx之前的加油站
//        for (int i = 0; i < startIdx; i++) {
//            curGas += gas[i] - cost[i];
//            if (curGas < 0) {
//                return -1;
//            }
//        }
//
//        return startIdx;

        int startIdx = 0;
        int curGas = 0;
        for (int i = 0; i < gas.length; i++) {
            curGas += gas[i] - cost[i];
            if (curGas < 0) {
                startIdx = i + 1;
                curGas = 0;
            }
        }

        for (int j = 0; j < startIdx; j++) {
            curGas += gas[j] - cost[j];
            if (curGas < 0)
                return -1;
        }
        return startIdx;
    }

    public int canRun(int[] gas, int[] cost) {
        int result = 0;
        int current = 0;
        int total = 0;
        for (int i = 0; i < gas.length; i++) {
            current += gas[i] - cost[i];
            total += gas[i] - cost[i];
            if (current < 0) {
                current = 0;
                result = i + 1;
            }
        }
        if (total >= 0) {
            return result;
        } else {
            return -1;
        }
    }


    public static int romanToInt(String s) {
        int I = 1;
        int V = 5;
        int X = 10;
        int L = 50;
        int C = 100;
        int D = 500;
        int M = 1000;
        int count = 0;
        char[] charArray = s.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            char c = charArray[i];
            if (c == 'I') {
                count += I;
                continue;
            }
            if (c == 'V') {
                if (i != 0 && charArray[i - 1] == 'I') {
                    count += V - 2 * I;
                    continue;
                }
                count += V;
                continue;
            }
            if (c == 'X') {
                if (i != 0 && charArray[i - 1] == 'I') {
                    count += X - 2 * I;
                    continue;
                }

                count += X;
                continue;
            }
            if (c == 'L') {
                if (i != 0 && charArray[i - 1] == 'X') {
                    count += L - 2 * X;
                    continue;
                }

                count += L;
                continue;
            }
            if (c == 'C') {
                if (i != 0 && charArray[i - 1] == 'X') {
                    count += C - 2 * X;
                    continue;
                }

                count += C;
                continue;
            }
            if (c == 'D') {

                if (i != 0 && charArray[i - 1] == 'C') {
                    count += D - 2 * C;
                    continue;
                }
                count += D;
                continue;
            }
            if (c == 'M') {

                if (i != 0 && charArray[i - 1] == 'C') {
                    count += M - 2 * C;
                    continue;
                }

                count += M;

            }

        }


        return count;
    }


    public static String intToRoman(int num) {
        int thousand = num / 1000;
        int hundred = (num / 100) % 10;
        int ten = (num / 10) % 10;
        int unit = num % 10;
        StringBuffer stringBuffer = new StringBuffer();
        //千位
        if (thousand != 0) {
            for (int i = 0; i < thousand; i++) {
                stringBuffer.append('M');
            }
        }
//百位
        if (hundred != 0) {

            if (hundred < 5) {
                if (hundred == 4) {
                    stringBuffer.append("CD");
                } else {
                    for (int i = 0; i < hundred; i++) {
                        stringBuffer.append('C');
                    }
                }

            } else {
                if (hundred == 9) {
                    stringBuffer.append("CM");
                } else {
                    stringBuffer.append("D");
                    for (int i = 0; i < hundred - 5; i++) {
                        stringBuffer.append('C');
                    }
                }

            }
        }
//十位
        if (ten != 0) {

            if (ten < 5) {
                if (ten == 4) {
                    stringBuffer.append("XL");
                } else {
                    for (int i = 0; i < ten; i++) {
                        stringBuffer.append('X');
                    }
                }

            } else {
                if (ten == 9) {
                    stringBuffer.append("XC");
                } else {
                    stringBuffer.append("L");
                    for (int i = 0; i < ten - 5; i++) {
                        stringBuffer.append('X');
                    }
                }

            }
        }
//个位
        if (unit != 0) {

            if (unit < 5) {
                if (unit == 4) {
                    stringBuffer.append("IV");
                } else {
                    for (int i = 0; i < unit; i++) {
                        stringBuffer.append('I');
                    }
                }

            } else {
                if (unit == 9) {
                    stringBuffer.append("IX");
                } else {
                    stringBuffer.append("V");
                    for (int i = 0; i < unit - 5; i++) {
                        stringBuffer.append('I');
                    }
                }

            }
        }
        return stringBuffer.toString();

    }

    public static int lengthOfLastWord(String s) {
//       int count=0;
//        String string = new StringBuffer(s).reverse().toString();
//        for(char c: string.toCharArray()){
//
//            if (c==' ') {
//                if (count!=0)
//                    break;
//            }else {
//                count++;
//            }
//
//
//        }
//        return count;
//        String sr=s.trim();
//        return  sr.length()-s.lastIndexOf(" ")-1;
        s = s.trim();
        return s.length() - s.lastIndexOf(" ") - 1;
    }

    public static String longestCommonPrefix(String[] strs) {


        int index = 0;
        int minLengthIndex = 0;
        int count = 0;
        int arrayLength = strs.length;
        int minLength = Integer.MAX_VALUE;
        if (arrayLength == 1) {
            return strs[0];
        }

        for (int i = 0; i < strs.length; i++) {
            if (strs[i].length() < minLength) {
                minLength = strs[i].length();
                minLengthIndex = i;
            }

        }
        if (minLength == 0) {
            return "";
        }

        String minLengthString = strs[minLengthIndex];
        while (true) {

            for (int i = 0; i < arrayLength; i++) {
                if (strs[i].charAt(index) != minLengthString.charAt(index))
                    break;
                else
                    count++;


            }
            if (count == arrayLength) {
                index++;
                count = 0;
            } else {
                break;
            }
            if (index == minLength) {
                break;
            }

        }
        if (index == 0) {
            return "";
        } else {
            return minLengthString.substring(0, index);
        }


    }

    public static int strStr(String haystack, String needle) {
//        if (!haystack.contains(needle))
//            return -1;
//
//        int count=0;
//        int index=0;
//      while (index<haystack.length()){
//           for (int i = 0; i < needle.length(); i++) {
//               if (haystack.charAt(i+index)==needle.charAt(i)){
//                   count++;
//
//               }else {
//                   index++;
//                   break;
//               }
//
//           }
//          if (count==needle.length()){
//              return index;
//          }else {
//              count=0;
//          }
//
//
//
//
//
//       }
//
//      return  -1;
        return haystack.indexOf(needle);


    }


    public static String convert(String s, int numRows) {
        if (s.length() <= 1) {
            return s;
        }
        int cycleLength = numRows + numRows - 2;
        int startColIndex = 0;
        int length = s.length();
        int row = numRows;
        int col = ((length / cycleLength) + 1) * (numRows - 1) + 1;
        char result[][] = new char[row][col];
        for (int i = 0; i < s.length(); i++) {
            if (i % cycleLength == 0 && i != 0) {
                startColIndex = startColIndex + numRows - 1;
            }
            int k = i % cycleLength;
            if (k <= numRows - 1) {
                result[k][startColIndex] = s.charAt(i);
            } else {
                int offset = k - (numRows - 1);
                result[row - 1 - offset][startColIndex + offset] = s.charAt(i);
            }


        }

        StringBuffer stringBuffer = new StringBuffer();
        for (int i = 0; i < result.length; i++) { // 遍历行
            for (int j = 0; j < result[i].length; j++) {
                if (result[i][j] != '\u0000') {
                    stringBuffer.append(result[i][j]);

                }

            }


        }


        return stringBuffer.toString();


    }

    public static boolean isPalindrome(String s) {
        if (s.length() <= 1) {
            return true;
        }
        String lowerCaseTemp = s.toLowerCase();

        StringBuffer stringBuffer = new StringBuffer();

        for (char c : lowerCaseTemp.toCharArray()) {


            if (c >= 'a' && c <= 'z' || c >= '0' && c <= '9') {
                stringBuffer.append(c);
            }

        }


        String lowerCase = stringBuffer.toString();
        Stack<Character> stack = new Stack<>();
        for (char c : lowerCase.toCharArray()) {
            stack.push(c);
        }
        int count = 0;
        for (int i = 0; i < lowerCase.length() / 2; i++) {
            if (lowerCase.charAt(i) == stack.pop()) {
                count++;
            } else {
                break;
            }
        }
        return count == lowerCase.length() / 2;


    }

    public static boolean isSubsequence(String s, String t) {

        if (s.length() == 0) {
            return true;
        }
        if (t.length() == 0) {
            return false;
        }

        int index = 0;
        for (char c : t.toCharArray()) {
            if (c == s.charAt(index)) {
                index++;
                if (index == s.length() - 1) {
                    return true;
                }
            }
        }
        return false;


    }

    public static int[] twoSum2(int[] numbers, int target) {
        int left = 0;
        Boolean flag = false;
        int rightStart = numbers.length - 1;
        int right = rightStart;
        int result[] = new int[2];
        while (true) {

            if (numbers[left] + numbers[right] < target) {
                left = left + 1;
                right = rightStart;
            } else if (numbers[left] + numbers[right] > target) {
                right--;
            } else {
                flag = true;
                break;

            }
            if (left == right) {
                left++;
                right = rightStart;
            }

        }
        if (flag) {
            result[0] = left + 1;
            result[1] = right + 1;
        }
        return result;

    }


    public static int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        int result[] = new int[2];
        while (left < right) {
            if (numbers[left] + numbers[right] > target) {
                right--;
            } else if (numbers[left] + numbers[right] < target) {
                left++;
            } else {
                result[0] = left + 1;
                result[1] = right + 1;
                break;
            }
        }
        return result;


    }

    public static List<List<Integer>> threeSum(int[] nums) {


        List<List<Integer>> results = new ArrayList<>();

        List<Integer> cur = new ArrayList<>();


        for (int i : nums) {
            cur.add(i);
        }

        Collections.sort(cur);
        for (int i = 0; i < cur.size(); i++) {
            if (i > 0 && cur.get(i) == cur.get(i - 1))
                continue;

            int sumResult = -cur.get(i);
            cur.remove(i);

            int left = 0;
            int right = cur.size() - 1;
            while (left < right) {

                int leftValue = cur.get(left);
                if (left - 1 >= 0 && cur.get(left - 1) == cur.get(left)) {
                    left++;
                    continue;
                }
                int rightValue = cur.get(right);
                if (right + 1 < cur.size() && cur.get(right + 1) == cur.get(right)) {
                    right--;
                    continue;
                }

                if ((leftValue + rightValue) > sumResult) {
                    right--;
                } else if ((leftValue + rightValue) < sumResult) {
                    left++;
                } else {
                    List<Integer> result = new ArrayList<>();
                    result.add(leftValue);
                    result.add(rightValue);
                    result.add(-sumResult);
                    results.add(new ArrayList<>(result));
                    right--;
                    left++;
                    result.removeAll(result);

                }
            }
            cur.add(-sumResult);
            Collections.sort(cur);


        }


        List<List<Integer>> resultReal = new ArrayList<>();

        for (int index = 0; index < results.size(); index++) {
            List list = results.get(index);
            Collections.sort(list);
            if (!resultReal.contains(list)) {
                resultReal.add(list);
            }

        }


        return resultReal;


    }

    public static int minSubArrayLen(int target, int[] nums) {

        int runSum = 0;
        int startSum = 0;
        for (int length = 1; length <= nums.length; length++) {
            for (int right = length - 1; right <= nums.length - 1; right++) {

                if (right == length - 1) {
                    startSum = startSum + nums[length - 1];
                    if (startSum >= target)
                        return length;
                    runSum = startSum;
                } else {
                    runSum = runSum + nums[right] - nums[right - length];
                    if (runSum >= target)
                        return length;
                }

            }
        }

        return 0;

    }

    public static int minSubArrayLen2(int target, int[] nums) {

        int minLength = Integer.MAX_VALUE;
        int sum = 0;
        for (int left = 0; left < nums.length; left++) {
            sum = nums[left];
            if (sum >= target) {
                return 1;
            }
            for (int right = left + 1; right < nums.length; right++) {
                sum += nums[right];
                if (sum >= target) {
                    int length = right - left + 1;
                    minLength = Math.min(length, minLength);
                    break;
                }
            }
        }
        minLength = minLength != Integer.MAX_VALUE ? minLength : 0;
        return minLength;

    }

    public static int minSubArrayLen3(int target, int[] nums) {
//        int left = 0;
//        int right = 0;
//        int minLength = Integer.MAX_VALUE;
//        int curSum = 0;
//        while (right < nums.length) {
//            curSum += nums[right];
//            while (curSum >= target) {
//                int length = right - left + 1;
//                curSum -= nums[left];
//                left++;
//                minLength = Math.min(length, minLength);
//            }
//            right++;
//
//        }
//        minLength = minLength != Integer.MAX_VALUE ? minLength : 0;
//        return minLength;
        int slowIndex = 0;
        int fastIndex = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;
        while (fastIndex < nums.length) {
            sum += nums[fastIndex++];
            while (sum >= target) {
                sum -= nums[slowIndex++];
                minLength = Math.min(minLength, fastIndex - slowIndex + 1);
            }
        }

        return minLength != Integer.MAX_VALUE ? minLength : 0;


    }

    public static int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        if (s.length() == 0 || s.length() == 1) {
            return s.length();
        }
        int left = 0;
        int right = 0;
        String temp = "";
        while (right < s.length()) {
            String c = "" + s.charAt(right);


            while (temp.contains(c)) {
                maxLength = Math.max(temp.length(), maxLength);
                left++;
                if (left == s.length()) {
                    break;
                }
                temp = s.substring(left, right);

            }
            temp += c;

            right++;

        }
        maxLength = maxLength != 0 ? maxLength : s.length();
        return maxLength;


    }

    public static boolean canConstruct(String ransomNote, String magazine) {
//        HashMap<Character, Integer> ransomNoteMap  = new HashMap<>();
//        HashMap<Character, Integer> magazineMap  = new HashMap<>();
//        for(Character c:ransomNote.toCharArray()){
//            ransomNoteMap.put(c,ransomNoteMap.getOrDefault(c,0)+1);
//
//        }
//        for(Character c:magazine.toCharArray()){
//            magazineMap.put(c,magazineMap.getOrDefault(c,0)+1);
//
//        }
//       Set<Character> keys=ransomNoteMap.keySet();
//        for(Character c:keys){
//            int i = ransomNoteMap.get(c);
//            int k = magazineMap.getOrDefault(c,0);
//            if (i>k){
//                return  false;
//            }
//        }
//        return true;


        int[] letter = new int[26];
        for (char ch : ransomNote.toCharArray()) {
            int i = magazine.indexOf(ch, letter[ch - 'a']);
            if (i == -1) {
                return false;
            } else {
                letter[ch - 'a'] = i + 1;
            }
        }
        return true;


    }

    public static boolean isIsomorphic(String s, String t) {

        HashMap<Character, Character> map = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                if (t.charAt(i) == map.get(s.charAt(i))) {
                    continue;
                } else {
                    return false;
                }

            } else {
                map.put(s.charAt(i), t.charAt(i));
            }


        }

        HashMap<Character, Character> map2 = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            if (map2.containsKey(t.charAt(i))) {
                if (s.charAt(i) == map2.get(t.charAt(i))) {
                    continue;
                } else {
                    return false;
                }

            } else {
                map2.put(t.charAt(i), s.charAt(i));
            }


        }


        return true;
    }

    public static boolean wordPattern(String pattern, String s) {
        String[] newString = s.split(" ");
        Map<Character, String> map = new HashMap<>();
        if (pattern.length() != newString.length)
            return false;

        for (int i = 0; i < pattern.length(); i++) {
            if (map.containsKey(pattern.charAt(i))) {
                if (newString[i].equals(map.get(pattern.charAt(i)))) {
                    continue;
                } else {
                    return false;
                }

            } else if (map.containsValue(newString[i])) {
                if (map.containsKey(pattern.charAt(i))) {
                    String s1 = map.get(pattern.charAt(i));
                    if (newString[i].equals(s1)) {
                        continue;
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }


            } else {
                map.put(pattern.charAt(i), newString[i]);
            }
        }
        return true;


    }

    public static boolean isAnagram(String s, String t) {
//    if (s.length()!=t.length())
//        return false;
//       List<Character> list=new ArrayList<>();
//       for(Character c:s.toCharArray()){
//           list.add(c);
//       }
//
//        List<Character> list2=new ArrayList<>();
//        for(Character c:t.toCharArray()){
//            list2.add(c);
//        }
//      Collections.sort(list);
//      Collections.sort(list2);
//      for(int i=0;i<s.length();i++){
//          if (list2.get(i)!=list.get(i)){
//              return false;
//          }
//      }
//        return true;


//        HashMap<Character, Integer> targetMap = new HashMap<>();
//        HashMap<Character, Integer> map = new HashMap<>();
//        for (Character c:s.toCharArray()){
//            targetMap.put(c,targetMap.getOrDefault(c,0)+1);
//        }
//
//        for (Character c:t.toCharArray()){
//            map.put(c,map.getOrDefault(c,0)+1);
//        }
//        Set<Map.Entry<Character, Integer>> entrySet = targetMap.entrySet();
//        for(Map.Entry<Character,Integer> entry: entrySet){
//            Character key=entry.getKey();
//            int value=entry.getValue();
//            if (!map.containsKey(key)){
//                return false;
//            }else  if (map.get(key)!=value){
//                return false;
//
//            }
//
//        }
//
//        return true;
        if (s.length() != t.length())
            return false;
        int[] nums = new int[26];
        for (char c : s.toCharArray()) {
            nums[c - 'a']++;
        }
        for (char c : t.toCharArray()) {
            nums[c - 'a']--;
        }

        for (int i : nums) {
            if (i != 0) {
                return false;
            }
        }
        return true;

    }

    public static int findTemp(int n) {


        if (n%10==0){
            n=n/10;
        }
        if (n==10||n==1){
            return 1;
        }




        int[] arr = new int[31];
        int index = 0;
        int result = 0;
        for (int i = 0; i < arr.length; i++) {
           int temp=n%10;
            arr[i] = temp;

            n/=10;
            if (n==0){
                index=i+1;
            }



        }
        for (int j = 0; j < index; j++) {
            result += arr[j] * arr[j];
        }
        return result;


    }


    public static boolean isHighestBitOne(int n) {
        // 如果n为0，最高位不是1
        if (n == 0) {
            return false;
        }

        // 如果n为1，最高位是1
        if (n == 1) {
            return true;
        }

        // 将n右移，直到最高位的1移动到最低位
        while (n > 1) {
            n = n /10 ; // 右移一位
        }

        // 如果右移后的n为1，则原始数的最高位是1
        return n == 1;
    }





    public static boolean isHappy(int n) {


        int count = 0;
        boolean flag=true;
        if(n==1)
            return true;

        while (flag) {
            n = findTemp(n);
            count++;
            if (n==1)
                return true;
            if (count == 30) {
                return false;
            }
            int k=n;
            if (n%10==0&&isHighestBitOne(k)){
                flag=false;
            }


        }
        return true;
    }

    public static List<List<String>> groupAnagrams(String[] strs) {
        int length = strs.length;
        int flag[] = new int[length];

        List<List<String>> results = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            List<String> strings = new ArrayList<>();
            if (flag[i] == 1) {
                continue;
            }
            flag[i] = 1;
            strings.add(strs[i]);
            for (int j = i + 1; j < length; j++) {
                if (flag[j] == 1)
                    continue;
                boolean anagram = isAnagram(strs[i], strs[j]);
                if (anagram) {

                    strings.add(strs[j]);
                    flag[j] = 1;
                }
            }
            results.add(strings);


        }
        return results;

    }


    public static void main(String[] args) {
//        int a[] = {1, 2, 3, 4};
//        System.out.println(Arrays.toString(productExceptSelf(a)));
//
//
//        int gas[] = {1, 2, 3, 4, 5};
//        int cost[] = {3, 4, 5, 1, 2};
//        System.out.println(canCompleteCircuit3(gas, cost));

//        System.out.println(intToRoman(1994));
//        String s = "   fly me   to   the moon  ";
//        String s1 = "Hello World";
//        String s2 = "luffy is still joyboy";
//        System.out.println(lengthOfLastWord(s1));
//        System.out.println(lengthOfLastWord(s));
//        System.out.println(lengthOfLastWord(s2));

//        String strs[] = {"dog", "racecar", "car"};
//        System.out.println(longestCommonPrefix(strs));

//        String s = "PAYPALISHIRING";
//        int numRows = 4;
//        String result = convert(s, numRows);

//        String haystack = "mississippi";
//        String needle = "sipp";
//        System.out.println(strStr(haystack,needle));
//        String s = "A man, a plan, a canal: Panama";

//        String s = "abc";
//        String t = "ahbgdc";
//        int[] numbers = {-5,-1,-5,-4,2,1,-1,2,-4,-3,-2,-4};
//        List<List<Integer>> lists = threeSum(numbers);
//
//        for (List<Integer> sublist : lists) {
//            sublist.stream().forEach(System.out::print);
//            System.out.println();
//        }

//        int nums[] = {4, 9};
//        System.out.println(minSubArrayLen3(9,nums));


//        String s = "rat";
//        String s2 = "car";
//        System.out.println(isAnagram(s, s2));

//        String strs[] = {"eat", "tea", "tan", "ate", "nat", "bat"};
//        List<List<String>> lists = groupAnagrams(strs);
//        for(List<String> list:lists){
////            list.forEach(item -> System.out.println(item) );
////            list.forEach(System.out::print);
//            list.forEach(item-> System.out.print(item));
//
//            System.out.println();
//        }

        int n =101;
        System.out.println(isHappy(n));


    }
}
